﻿/*************************************************************************
 * R-Tree/R*-Tree 包围盒
 * 
 * @author lmliang@live.cn
 *************************************************************************/
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace RStarTree
{
    /// <summary>
    /// R*-Tree
    /// </summary>
    /// <typeparam name="TLeaf">叶子类型</typeparam>
    partial class RStarTree<TLeaf>
    {
        /// <summary>
        /// RTree包围盒
        /// </summary>
        private class RTreeBoundingBox
        {
            /// <summary>
            /// 维度
            /// </summary>
            public Int32 Dimension { get { return AxisRange.Length; } }

            /// <summary>
            /// 维度的范围
            /// </summary>
            public Range[] AxisRange;

            /// <summary>
            /// 构造
            /// </summary>
            /// <param name="dimension">维度，>=2</param>
            public RTreeBoundingBox(Int32 dimension)
            {
                Debug.Assert(dimension >= 2);

                AxisRange = new Range[dimension];
                for (int i = 0; i < dimension; ++i)
                    AxisRange[i] = new Range(Double.MaxValue, Double.MinValue);
            }

            /// <summary>
            /// 构造
            /// </summary>
            /// <param name="bound">各维度范围</param>
            public RTreeBoundingBox(Double[] bound)
            {
                Int32 dimension = bound.Length / 2;
                Debug.Assert(dimension >= 2);

                AxisRange = new Range[dimension];
                for (int i = 0; i < AxisRange.Length; ++i)
                    AxisRange[i] = new Range(bound[i * 2], bound[i * 2 + 1]);
            }

            /// <summary>
            /// 拷贝构造
            /// </summary>
            /// <param name="bound">包围盒</param>
            public RTreeBoundingBox(RTreeBoundingBox bound)
            {
                Debug.Assert(bound.Dimension >= 2);

                AxisRange = new Range[bound.Dimension];
                for (int i = 0; i < AxisRange.Length; ++i)
                    AxisRange[i] = new Range(bound.AxisRange[i].Min, bound.AxisRange[i].Max);
            }

            /// <summary>
            /// 重置
            /// </summary>
            public void Reset()
            {
                foreach (Range r in AxisRange)
                {
                    r.Min = Double.MaxValue;
                    r.Max = Double.MinValue;
                }
            }
            /// <summary>
            /// 边长
            /// </summary>
            /// <returns>边长</returns>
            public Double Margin()
            {
                Double margin = 0.0;

                for (int i = 0; i < Dimension; ++i)
                    margin += AxisRange[i].Interval();

                return margin;
            }
            /// <summary>
            /// 面积
            /// </summary>
            /// <returns>面积</returns>
            public Double Area()
            {
                Double area = 1.0;

                for (int i = 0; i < Dimension; ++i)
                    area *= AxisRange[i].Interval();

                return area;
            }
            /// <summary>
            /// 拉伸使给定包围盒包含在内部
            /// </summary>
            /// <param name="bound">给定包围盒</param>
            /// <returns>发生拉伸返回true，否则返回false</returns>
            public Boolean Stretch(RTreeBoundingBox bound)
            {
                Debug.Assert(Dimension == bound.Dimension);

                Boolean stretched = false;

                for (int i = 0; i < Dimension; ++i)
                {
                    if (AxisRange[i].Min > bound.AxisRange[i].Min)
                    {
                        AxisRange[i].Min = bound.AxisRange[i].Min;
                        stretched = true;
                    }

                    if (AxisRange[i].Max < bound.AxisRange[i].Max)
                    {
                        AxisRange[i].Max = bound.AxisRange[i].Max;
                        stretched = true;
                    }
                }

                return stretched;
            }
            /// <summary>
            /// 给定包围盒是否完全包含在内部
            /// </summary>
            /// <param name="bound">给定包围盒</param>
            /// <returns>完全包含返回true，否则返回false</returns>
            public Boolean Enclosed(RTreeBoundingBox bound)
            {
                Debug.Assert(Dimension == bound.Dimension);

                for (int i = 0; i < Dimension; ++i)
                {
                    if (bound.AxisRange[i].Min < AxisRange[i].Min || bound.AxisRange[i].Max > AxisRange[i].Max)
                        return false;
                }

                return true;
            }
            /// <summary>
            /// 和给定包围盒是否有重叠
            /// </summary>
            /// <param name="bound">给定包围盒</param>
            /// <returns>重叠返回true，否则返回false</returns>
            public Boolean Overlapped(RTreeBoundingBox bound)
            {
                Debug.Assert(Dimension == bound.Dimension);

                for (int i = 0; i < Dimension; ++i)
                {
                    if (!(AxisRange[i].Min < bound.AxisRange[i].Max) || !(AxisRange[i].Max > bound.AxisRange[i].Min))
                        return false;
                }

                return true;
            }
            /// <summary>
            /// 与给定包围盒的重叠的面积
            /// </summary>
            /// <param name="bound">给定包围盒</param>
            /// <returns>重叠面积</returns>
            public Double OverlapArea(RTreeBoundingBox bound)
            {
                Debug.Assert(Dimension == bound.Dimension);

                Double area = 1.0;

                for (int i = 0; area != 0.0 && i < Dimension; ++i)
                {
                    Double min = AxisRange[i].Min;
                    Double max = AxisRange[i].Max;
                    Double mine = bound.AxisRange[i].Min;
                    Double maxe = bound.AxisRange[i].Max;

                    if (min < mine)
                    {
                        if (mine < max)
                        {
                            if (max < maxe)
                                area *= (max - mine);
                            else
                                area *= (maxe - mine);
                            continue;
                        }
                    }
                    else if (min < maxe)
                    {
                        if (maxe < max)
                            area *= (maxe - min);
                        else
                            area *= (max - min);
                        continue;
                    }

                    return 0.0;
                }

                return area;
            }
            /// <summary>
            /// 各维度中点距离
            /// </summary>
            /// <param name="bound">给定包围盒</param>
            /// <returns>距离</returns>
            public Double CenterDistance(RTreeBoundingBox bound)
            {
                Debug.Assert(Dimension == bound.Dimension);

                Double dist = 0.0;

                for (int i = 0; i < Dimension; ++i)
                {
                    Double t = ((AxisRange[i].Min + AxisRange[i].Max)
                        - (bound.AxisRange[i].Min + bound.AxisRange[i].Max)) / 2.0;
                    dist += (t * t);
                }

                return dist;
            }
            /// <summary>
            /// 包围盒是否相同
            /// </summary>
            /// <param name="bound">给定包围盒</param>
            /// <returns>相同返回true，否则返回false</returns>
            public Boolean Equals(RTreeBoundingBox bound)
            {
                Debug.Assert(Dimension == bound.Dimension);
                if (Dimension != bound.Dimension)
                    return false;

                for (int i = 0; i < Dimension; ++i)
                {
                    if (AxisRange[i].Min != bound.AxisRange[i].Min || AxisRange[i].Max != bound.AxisRange[i].Max)
                        return false;
                }

                return true;
            }
        }

        /// <summary>
        /// 范围
        /// </summary>
        private class Range
        {
            /// <summary>
            /// 最小值
            /// </summary>
            public Double Min { get; set; }
            /// <summary>
            /// 最大值
            /// </summary>
            public Double Max { get; set; }
            /// <summary>
            /// 构造
            /// </summary>
            /// <param name="min"></param>
            /// <param name="max"></param>
            public Range(Double min, Double max)
            {
                Min = min;
                Max = max;
            }
            /// <summary>
            /// 间距
            /// </summary>
            /// <returns>间距</returns>
            public Double Interval()
            {
                return Max - Min;
            }
        }

        /// <summary>
        /// 按照重叠拉伸进行排序
        /// </summary>
        private class SortItemsByOverlapEnlargement : IComparer<RTreeBoundingBox>
        {
            public SortItemsByOverlapEnlargement(RTreeBoundingBox bound)
            {
                baseBound = bound;
            }

            public Int32 Compare(RTreeBoundingBox bound1, RTreeBoundingBox bound2)
            {
                Debug.Assert(baseBound.Dimension == bound1.Dimension
                    && baseBound.Dimension == bound2.Dimension);

                Double area1 = baseBound.OverlapArea(bound1);
                Double area2 = baseBound.OverlapArea(bound2);

                if (area1 < area2)
                    return -1;
                else if (area1 > area2)
                    return 1;
                else
                    return 0;
            }

            private RTreeBoundingBox baseBound;
        }

        /// <summary>
        /// 按照拉伸面积排序
        /// </summary>
        private class SortItemsByAreaEnlargement : IComparer<RTreeBoundingBox>
        {
            public SortItemsByAreaEnlargement(RTreeBoundingBox bound)
            {
                baseBound = bound;
            }

            public Int32 Compare(RTreeBoundingBox bound1, RTreeBoundingBox bound2)
            {
                Debug.Assert(baseBound.Dimension == bound1.Dimension
                    && baseBound.Dimension == bound2.Dimension);

                RTreeBoundingBox enbound1 = new RTreeBoundingBox(baseBound);
                RTreeBoundingBox enbound2 = new RTreeBoundingBox(baseBound);
                enbound1.Stretch(bound1);
                enbound2.Stretch(bound2);
                Double enlarge1 = enbound1.Area() - baseBound.Area();
                Double enlarge2 = enbound2.Area() - baseBound.Area();

                if (enlarge1 < enlarge2)
                    return -1;
                else if (enlarge1 > enlarge2)
                    return 1;
                else
                    return 0;
            }

            private RTreeBoundingBox baseBound;
        }

        /// <summary>
        /// 按照某一维度的最小值排序
        /// </summary>
        private class SortItemsByAxisMin : IComparer<RTreeBoundingBox>
        {
            /// <summary>
            /// 构造
            /// </summary>
            /// <param name="axisIndex">轴索引, 0~dimension-1</param>
            public SortItemsByAxisMin(Int32 axisIndex)
            {
                AxisIndex = axisIndex;
            }

            public Int32 Compare(RTreeBoundingBox bound1, RTreeBoundingBox bound2)
            {
                Debug.Assert(AxisIndex < bound1.Dimension && bound1.Dimension == bound2.Dimension);
                if (bound1.AxisRange[AxisIndex].Min < bound2.AxisRange[AxisIndex].Min)
                    return -1;
                else if (bound1.AxisRange[AxisIndex].Min > bound2.AxisRange[AxisIndex].Min)
                    return 1;
                else
                    return 0;
            }

            private Int32 AxisIndex;
        }

        /// <summary>
        /// 按照某一维度的最大值排序
        /// </summary>
        private class SortItemsByAxisMax : IComparer<RTreeBoundingBox>
        {
            /// <summary>
            /// 构造
            /// </summary>
            /// <param name="axisIndex">轴索引, 0~dimension-1</param>
            public SortItemsByAxisMax(Int32 axisIndex)
            {
                AxisIndex = axisIndex;
            }

            public Int32 Compare(RTreeBoundingBox bound1, RTreeBoundingBox bound2)
            {
                Debug.Assert(AxisIndex < bound1.Dimension && bound1.Dimension == bound2.Dimension);
                if (bound1.AxisRange[AxisIndex].Max < bound2.AxisRange[AxisIndex].Max)
                    return -1;
                else if (bound1.AxisRange[AxisIndex].Max > bound2.AxisRange[AxisIndex].Max)
                    return 1;
                else
                    return 0;
            }

            private Int32 AxisIndex;
        }

        /// <summary>
        /// 按照中点距离排序
        /// </summary>
        private class SortItemsByCenterDistance : IComparer<RTreeBoundingBox>
        {
            public SortItemsByCenterDistance(RTreeBoundingBox bound)
            {
                baseBound = bound;
            }

            public Int32 Compare(RTreeBoundingBox bound1, RTreeBoundingBox bound2)
            {
                Debug.Assert(baseBound.Dimension == bound1.Dimension && baseBound.Dimension == bound2.Dimension);

                Double dist1 = baseBound.CenterDistance(bound1);
                Double dist2 = baseBound.CenterDistance(bound2);

                if (dist1 < dist2)
                    return -1;
                else if (dist1 > dist2)
                    return 1;
                else
                    return 0;
            }

            private RTreeBoundingBox baseBound;
        }
    }
}